import {
  TBinaryTreeNode,
  BinaryTreeNode,
} from './base';
import {
  LESS_THAN,
  BIGGER_THAN,
} from '../utils/constant';
import {
  TCompareFunc,
  defaultCompare,
} from '../utils/tools';

type TCallback = DSAATree.TTraverseCB;

export class BinarySearchTree {
  protected root: TBinaryTreeNode;
  protected funcCompare: TCompareFunc;

  public constructor(elements: any[] = [], funcCompare?: TCompareFunc) {
    this.funcCompare = funcCompare || defaultCompare;
    this.root = null;
    
    for (let val of elements) {
      this.insert(val);
    }
  }

  public insert(key) {
    if (!this.root) {
      this.root = new BinaryTreeNode(key);
    } else {
      this.root = this.insertNode(this.root, key);
    }
  }

  public search(key) {
    const result = this.searchNode(key, this.root);

    return !!result;
  }

  public inOrderTraverse(cb: TCallback = () => {}) {
    function inOrderTraverseNode(node: TBinaryTreeNode, cb: TCallback) {
      if (node) {
        inOrderTraverseNode(node.left, cb);
        cb(node.key, node?.left?.key, node?.right?.key);
        inOrderTraverseNode(node.right, cb);
      }
    }
    
    inOrderTraverseNode(this.root, cb);
  }

  public preOrderTraverse(cb: TCallback = () => {}) {
    function preOrderTraverseNode(node: TBinaryTreeNode, cb: TCallback) {
      if (node) {
        cb(node.key, node?.left?.key, node?.right?.key);
        preOrderTraverseNode(node.left, cb);
        preOrderTraverseNode(node.right, cb);
      }
    }
    
    preOrderTraverseNode(this.root, cb);
  }

  public postOrderTraverse(cb: TCallback) {
    function postOrderTraverseNode(node: TBinaryTreeNode, cb: TCallback) {
      if (node) {
        postOrderTraverseNode(node.left, cb);
        postOrderTraverseNode(node.right, cb);
        cb(node.key, node?.left?.key, node?.right?.key);
      }
    }
    
    postOrderTraverseNode(this.root, cb);
  }

  public min() {
    return this.minNode(this.root)?.key;
  }

  public max() {
    return this.maxNode(this.root)?.key;
  }

  public remove(key: any) {
    this.root = this.removeNode(key, this.root);
  }

  public getNodeHeight(target: TBinaryTreeNode | any) {
    const node = target instanceof BinaryTreeNode ? target : this.searchNode(target, this.root)?.node;

    if (node) {
      const left = node.left;
      const right = node.right;
      let leftH = this.getNodeHeight(node.left);
      let rightH = this.getNodeHeight(node.right);

      if (!left && !right) {
        return 0;
      } else {
        return Math.max(leftH, rightH) + 1;
      }
    } else {
      return -1;
    }
  }

  protected insertNode(node: TBinaryTreeNode, key: any): TBinaryTreeNode {
    let newNode = node;
    
    if (newNode) {
      if (this.funcCompare(key, newNode.key) === LESS_THAN) {
        const leftNode = newNode.left;
  
        if (!leftNode) {
          newNode.left = new BinaryTreeNode(key);
        } else {
          newNode.left = this.insertNode(leftNode, key);
        }
      } else if (this.funcCompare(key, newNode.key) === BIGGER_THAN) {
        const rightNode = newNode.right;
  
        if (!rightNode) {
          newNode.right = new BinaryTreeNode(key);
        } else {
          newNode.right = this.insertNode(rightNode, key);
        }
      }
    }

    return newNode;
  }

  protected minNode(node: TBinaryTreeNode): TBinaryTreeNode {
    let min = node;
    let left = min?.left;

    while(left) {
      min = left;
      left = min?.left;
    }
    
    return min;
  }

  protected maxNode(node: TBinaryTreeNode): TBinaryTreeNode {
    let max = node;
    let right = max?.right;

    while(right) {
      max = right;
      right = max?.right;
    }
    
    return max;
  }

  protected searchNode(key: any, node: TBinaryTreeNode, parentNode?: TBinaryTreeNode): null | undefined | {
    node: TBinaryTreeNode,
    parentNode: TBinaryTreeNode,
  } {
    if (node) {
      const compareResult = this.funcCompare(key, node.key);
      if (compareResult === LESS_THAN) {
        const left = node.left;

        if (left) {
          return this.searchNode(key, left, node);
        } else {
          return undefined;
        }
      } else if (compareResult === BIGGER_THAN) {
        const right = node.right;

        if (right) {
          return this.searchNode(key, right, node);
        } else {
          return undefined;
        }
      } else {
        return {
          node,
          parentNode,
        };
      }
    } else {
      return undefined;
    }
  }

  protected removeNode(key: any, node: TBinaryTreeNode) {
    const setChild = (parent: TBinaryTreeNode, child: BinaryTreeNode, newChild: TBinaryTreeNode) => {
      if (parent) {
        if (parent.left === child) {
          parent.left = newChild;
        } else if (parent.right === child) {
          parent.right = newChild;
        }
      } else {
        this.root = newChild;
      }
    };

    let resultSearch = this.searchNode(key, node);
    let keyNode = resultSearch?.node;
    let parentNode = resultSearch?.parentNode;

    if (keyNode) {
      const left = keyNode.left;
      const right = keyNode.right;

      if (!left && !right) {
        setChild(parentNode, keyNode, null);
      } else if (left && !right) {
        setChild(parentNode, keyNode, keyNode.left);
      } else if (right && !left) {
        setChild(parentNode, keyNode, keyNode.right);
      } else if (left && right) {
        const aux = this.minNode(right) as BinaryTreeNode;

        this.removeNode(aux.key, right);

        aux.left = left;
        aux.right = right;
        setChild(parentNode, keyNode, aux);
      }
    }

    return parentNode ? node : this.root;
  }
}
